package com.github.hgkmail.hello.leetcode101.pointer.tree;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;
import com.github.hgkmail.hello.leetcode101.base.TreeNode;

public class LC617MergeTwoBinaryTrees {
    //先序遍历，从上到下
    public TreeNode dfs(TreeNode root1, TreeNode root2) {
        if (root1==null) {
            return root2;
        }
        if (root2==null) {
            return root1;
        }
        TreeNode freshNode=new TreeNode(root1.val+root2.val);
        freshNode.left=dfs(root1.left, root2.left);
        freshNode.right=dfs(root1.right, root2.right);

        return freshNode;
    }
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1==null) {
            return root2;
        }
        if (root2==null) {
            return root1;
        }
        return dfs(root1, root2);
    }

    public static void main(String[] args) {
        TreeNode root1 = CommonUtil.deserializeBinaryTree("1,3,5,#,#,#,2,#,#");
        TreeNode root2 = CommonUtil.deserializeBinaryTree("2,1,#,4,#,#,3,#,7,#,#");
        System.out.println(CommonUtil.serializeBinaryTree(new LC617MergeTwoBinaryTrees().mergeTrees(root1, root2)));
    }
}
